package List

import (
	"math/rand"
	"runtime"
	"time"
)

type Node struct { //定义节点
	Data interface{}
	Next *Node
}

//单链表
type AloneLinkList struct {
	length int
	header *Node
}

//创建一个单链表
func MakeAloneLinkList() AloneLinkList {
	header := Node{
		Data: nil,
		Next: nil,
	}

	return AloneLinkList{0, &header}

}

func (l *AloneLinkList) Insert(data interface{}, i int) error {
	if i > l.length || i < 0 {
		return InsertErr
	}

	p := l.header
	l.length += 1

	for j := 0; j <= i; j++ {
		if p.Next == nil { //出现中间为空节点直接尾插
			node := Node{data, nil}
			p.Next = &node
			return nil
		}
		p = p.Next
	}

	//创建并衔接
	node := Node{data, nil}
	node.Next = p.Next
	p.Next = &node
	return nil

}

func (l *AloneLinkList) GetElem(i int) (interface{}, error) {
	if i > l.length || i < 0 || l.length == 0 {
		return nil, IndexErr
	}

	if i == 0 {
		return l.header.Next.Data, nil
	}

	p := l.header
	for j := 0; j < i; j++ {
		p = p.Next
	}

	return p.Data, nil

}

func (l *AloneLinkList) Length() int {
	return l.length
}

//弹出节点
func (l *AloneLinkList) Pop(i int) (interface{}, error) {
	if i > l.length || i < 0 {
		return nil, NodeErr
	}

	p := l.header
	l.length -= 1

	for j := 0; j < i; j++ {
		p = p.Next
	}

	data := p.Next.Data
	p.Next = p.Next.Next //跳过一个节点

	return data, nil

}

//初始化一个长度为n的随机int链表
func NewAloneLinkListInitRangeInt(n int) AloneLinkList {
	alone := MakeAloneLinkList()

	rand.Seed(time.Now().Unix())
	for i := 0; i < n; i++ {
		alone.Insert(rand.Intn(10), 0)
	}

	return alone

}

//尾插
func (l *AloneLinkList) Append(data interface{}) error {
	err := l.Insert(data, l.length)

	return err
}

//清空链表
func (l *AloneLinkList) Clear() {
	l.header.Next = nil
	l.length = 0
	runtime.GC()

}

//循环链表
type CircularLinkList struct {
	AloneLinkList
	rear *Node
}

//创建循环链表
func MakeCircularLinkList() CircularLinkList {
	header := Node{
		Data: nil,
	}

	header.Next = &header

	alone := AloneLinkList{
		length: 0,
		header: &header,
	}

	return CircularLinkList{alone, &header}

}

func NewCircularLinkListInitRangeInt(n int) CircularLinkList {
	alone := MakeCircularLinkList()

	rand.Seed(time.Now().Unix())
	for i := 0; i < n; i++ {
		alone.Insert(rand.Intn(10), 0)
	}

	return alone

}

func (l *CircularLinkList) Insert(data interface{}, i int) error {

	if data == nil {
		return DataErr
	}

	if i > l.length || i < 0 {
		return InsertErr
	}

	p := l.header
	l.length += 1

	for j := 0; j < i; j++ {
		if p.Next.Data == nil { //出现中间为空节点直接尾插
			node := Node{data, l.header}
			p.Next = &node
			l.rear = &node
			return nil
		}
		p = p.Next
	}

	//创建并衔接

	node := Node{data, nil}
	node.Next = p.Next
	p.Next = &node

	if node.Next.Data == nil { //最后一个节点更新l.rear
		l.rear = &node
	}

	return nil
}

func (l *CircularLinkList) Clear() {
	l.header.Next = l.header
	l.length = 0
	l.rear = l.header
	runtime.GC()

}

func (l *CircularLinkList) Pop(i int) (interface{}, error) {
	if i >= l.length || i < 0 {
		return nil, NodeErr
	}

	p := l.header

	for j := 0; j < i; j++ {
		p = p.Next
	}

	if i == l.length-1 { //处理最后
		data := p.Next.Data
		p.Next = l.header
		l.rear = p
		l.length -= 1
		return data, nil
	}

	data := p.Next.Data
	p.Next = p.Next.Next //跳过一个节点
	l.length -= 1

	return data, nil

}

//双向链表
type BoNode struct {
	Data interface{}
	Next *BoNode //下一节点
	Last *BoNode //上一节点
}

type BoLinkList struct {
	length int
	header *BoNode
}

//创建BoLinkList
func MakeBoLinkList() BoLinkList {
	node := BoNode{nil, nil, nil}

	link := BoLinkList{
		header: &node,
		length: 0,
	}

	return link

}

//插入数据
func (l *BoLinkList) Insert(data interface{}, i int) error {
	if i < 0 {
		return InsertErr
	}

	p := l.header
	l.length += 1

	for j := 0; j < i; j++ {
		if p.Next == nil { //出现中间为空节点直接尾插
			node := BoNode{data, nil, p}
			p.Next = &node
			return nil
		}
		p = p.Next
	}

	//创建并衔接
	node := BoNode{data, nil, p}
	node.Next = p.Next
	p.Next = &node
	return nil
}

//添加数据
func (l *BoLinkList) GetElem(i int) (interface{}, error) {
	if i > l.length || i < 0 || l.length == 0 {
		return nil, IndexErr
	}

	if i == 0 {
		return l.header.Next.Data, nil
	}

	p := l.header
	for j := 0; j < i; j++ {
		p = p.Next
	}

	return p.Data, nil

}

func (l *BoLinkList) Length() int {
	return l.length
}

func (l *BoLinkList) Clear() {
	l.header.Next = nil
	l.length = 0
	runtime.GC()

}

func (l *BoLinkList) Pop(i int) (interface{}, error) {
	if i > l.length || i < 0 {
		return nil, NodeErr
	}

	p := l.header
	l.length -= 1

	for j := 0; j < i; j++ {
		p = p.Next
	}

	data := p.Next.Data
	p.Next.Last = p
	p.Next = p.Next.Next //跳过一个节点

	return data, nil

}

func (l *BoLinkList) Append(data interface{}) error {
	err := l.Insert(data, l.length)

	return err
}
